P4197 Peaks

糅合了倍增、Kruskal重构树、可持久化线段树求区间第K大这些经典问题，是一道不错的练习题

题解：

这题由于比较复杂，先放上一张从这盗来的图，是样例的Kruskal重构树 ：

首先注意到只经过困难值小于等于$x$的路径这一限制，这是一个经典的Kruskal重构树问题

具体见上图：红点是实点，白点是虚点，红色数字是连接白点下方两个点的边的权值

很容易发现Kruskal重构树的一个性质：一棵子树里的所有红数字都是小于等于该子树根上的红数字的

现在题目给出了你起点$v$，和限制$x$，根据这个性质，就可以从红点$v$开始向上爬，直到爬到一个白点$p$，满足$p$的父亲的红色数字大于$x$或$p$没有父亲

至于爬的过程这又是一个经典问题，我们用倍增解决，可以使爬的过程复杂度从$O(n)$降为$O(\log n)$

在得到$p$点后，以$p$为根的子树内的所有红点就是起点$v$可以到达的点，现在的任务就是要快速求出一棵子树上的第$k$大数

由于所有的山峰高度都在叶子（即红点上），不难看出是有连续性的

观察上面的图，我们可以在建完重构树后从树根开始，从上往下跑一遍dfs

在把值插入主席树的同时，把所有的叶子拍扁，记录下所有白点所管辖的红点的范围

至于这个红点的范围，可以具体看图，从左到右，十分清楚

这样对于询问，就可以先根据$v$和$x$找出$p$，再在$p$的所管辖红点范围内做个区间第$k$大查询即可

另外在代码中，还有一个常规操作是要先将山峰高度离散化了再做

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return  x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

const int N=1e5+5,M=5e5+5;
int height[N<<1],rt[N],h[N<<1],en,un,cnt,f[N<<1],fa[N<<1][21],n,m,q,num[N],val[N],id,lef[N<<1],rig[N<<1];
int lc[N<<6],rc[N<<6],a[N<<6];

struct edge{
    int n,v;
}e[N<<1];

inline void add(int x,int y){
    e[++en]=(edge){h[x],y};
    h[x]=en;
}

struct ee{
    int x,y,z;
    inline bool operator < (const ee &nt) const {
        return z<nt.z;
    }
}data[M];

inline int getf(int x){
    if(f[x]==x) return x;
    return f[x]=getf(f[x]);
}
/*建基树*/
int build(int l,int r){
    int x=++cnt;
    if(l==r){
        return x;
    }
    int mid=l+r>>1;
    lc[x]=build(l,mid);
    rc[x]=build(mid+1,r);
    return x;
}
/*插入个数*/
int up(int pre,int l,int r,int p){
    int x=++cnt;
    lc[x]=lc[pre];
    rc[x]=rc[pre];
    a[x]=a[pre]+1;
    if(l==r){
        return x;
    }
    int mid=l+r>>1;
    if(p<=mid) lc[x]=up(lc[pre],l,mid,p);
    else rc[x]=up(rc[pre],mid+1,r,p);
    return x;
}
/*查询第k大*/
int que(int x,int y,int l,int r,int k){
    if(l==r) return l;
    int now=a[rc[y]]-a[rc[x]]; //看看较大的半边有多少个数 
    int mid=l+r>>1;
    if(now>=k) return que(rc[x],rc[y],mid+1,r,k); //够k个就往大的找（右边） 
    else return que(lc[x],lc[y],l,mid,k-now); //不够就砍掉右边的数量，再往小的找（左边） 
}
/*维护倍增所需信息，记录白点所管辖红点范围，将山峰高度插到主席树中*/
void dfs(int x){
    for(int i=1;i<=20;i++)
        fa[x][i]=fa[fa[x][i-1]][i-1];
    if(x<=n){
        int pos=lower_bound(num+1,num+1+un,val[x])-num;
        id++; //找到一个红点，范围+1 
        rt[id]=up(rt[id-1],1,un,pos); //把红点的山峰高度插到主席树中去 
    }
    else{
        lef[x]=id; //Attention!!!注意这边存是一个左开右闭区间 
        for(int i=h[x];i;i=e[i].n){
            int y=e[i].v;
            dfs(y);
        }
        rig[x]=id;
    }
}

void doit(){
    int s,x,k;
    read(s);read(x);read(k);
    for(int i=20;i>=0;i--) if(fa[s][i]&&height[fa[s][i]]<=x)
        s=fa[s][i]; //倍增找题解中所说的p点 
    if(rig[s]-lef[s]<k){ //如果管辖范围内根本不足k个点就无解 
        puts("-1");
        return ;
    }
    write(num[que(rt[lef[s]],rt[rig[s]],1,un,k)]);puts(""); //查询 
}

signed main(){
    read(n);read(m);read(q);
    for(int i=1;i<=n;i++)
        num[i]=read(val[i]);
    sort(num+1,num+1+n);
    un=unique(num+1,num+1+n)-num-1; //离散化 
    for(int i=1,x,y,z;i<=m;i++){
        read(x);read(y);read(z);
        data[i]=(ee){x,y,z};
    }
    sort(data+1,data+1+m);
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1,num=0;i<=m;i++){ //Krusakal
        int x=getf(data[i].x),y=getf(data[i].y);
        if(x==y) continue;
        num++;
        height[n+num]=data[i].z;
        f[x]=f[y]=f[n+num]=n+num; //n+num是虚点编号 
        add(n+num,x); //从上往下（从虚往实）连边 
        add(n+num,y);
        fa[x][0]=fa[y][0]=n+num;
        if(num==n-1) break;
    }
    rt[0]=build(1,un); //建基树 
    dfs(2*n-1); //2*n-1是深度最浅的虚点，即树根 
    while(q--) doit();
}